/*
Copyright (c) 2008, Mike Gashler

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/

#ifndef __GHASHTABLE_H__
#define __GHASHTABLE_H__

#include <stdio.h>
#ifndef WIN32
#	include <stdint.h>
#endif // WIN32
#include "string.h"
#include "app.h"

class GQueue;
class GPointerArray;
struct HashBucket;

// The base class of hash tables
class GHashTableBase
{
friend class GHashTableEnumerator;
protected:
	struct HashBucket* m_pBuckets;
	struct HashBucket* m_pFirstEmpty;
	int m_nBucketCount;
	int m_nCount;
	int m_nModCount;

	GHashTableBase(int nInitialBucketCount);

public:
	virtual ~GHashTableBase();

	int GetCount() { return m_nCount; }
	int GetModCount() { return m_nModCount; }

protected:
	virtual unsigned int Hash(const char* pKey, int nBucketCount) = 0;
	virtual bool AreKeysEqual(const char* pKey1, const char* pKey2) = 0;
	void _Resize(int nNewSize);

	// Adds a key/value pair to the hash table
	void _Add(const char* pKey, const void* pValue);

	// Returns true and the first occurrence of a value with the specified key if one exists
	bool _Get(const char* pKey, void** pOutValue);

	// Removes the first found occurrence of the specified key
	void _Remove(const char* pKey);

	// Returns the number of values with the specified key
	int _Count(const char* pKey);
};




#define UNCOMMON_INT 0x80000000

// This class makes it easy to iterate through the values in a hash table
class GHashTableEnumerator
{
protected:
	GHashTableBase* m_pHashTable;
	int m_nPos;
	int m_nModCount;

public:
	GHashTableEnumerator(GHashTableBase* pHashTable)
	{
		m_pHashTable = pHashTable;
		m_nModCount = m_pHashTable->GetModCount();
		m_nPos = 0;
	}

	// Gets the next element in the hash table. ppValue is set to
	// the value and the return value is the key. Returns NULL when
	// it reaches the end of the collection. (The first time it is
	// called, it returns the first item in the collection.)
	const char* GetNext(void** ppOutValue);

	// Returns the value associated with the current key
	void* GetCurrentValue();
};




// Implements a typical hash table. (It doesn't take ownership
// of the objects you add, so you must still delete them yourself.)
class GHashTable : public GHashTableBase
{
public:
	GHashTable(int nInitialBucketCount)
		: GHashTableBase(nInitialBucketCount)
	{
	}

	virtual ~GHashTable()
	{
	}

#ifndef NO_TEST_CODE
	static void Test();
#endif // !NO_TEST_CODE

	virtual unsigned int Hash(const char* pKey, int nBucketCount)
	{
		return (unsigned int)(((uintptr_t)pKey) % nBucketCount);
	}

	virtual bool AreKeysEqual(const char* pKey1, const char* pKey2)
	{
		return pKey1 == pKey2;
	}

	// Adds a pointer key and value pair to the hash table.  The key can not be NULL
	void Add(const void* pKey, const void* pValue)
	{
		_Add((const char*)pKey, pValue);
	}

	// Gets a value based on the key
	bool Get(const void* pKey, void** ppOutValue)
	{
		return _Get((const char*)pKey, ppOutValue);
	}

	// Removes an entry from the hash table
	void Remove(const void* pKey)
	{
		_Remove((const char*)pKey);
	}
};





// Hash table based on keys of constant strings (or at least strings
// that won't change during the lifetime of the hash table).  It's a
// good idea to use a GHeap in connection with this class.
class GConstStringHashTable : public GHashTableBase
{
protected:
	bool m_bCaseSensitive;

public:
	GConstStringHashTable(int nInitialBucketCount, bool bCaseSensitive)
		: GHashTableBase(nInitialBucketCount)
	{
		m_bCaseSensitive = bCaseSensitive;
	}

	virtual ~GConstStringHashTable()
	{
	}

	virtual unsigned int Hash(const char* pKey, int nBucketCount)
	{
		unsigned int n = 0;
		if(m_bCaseSensitive)
		{
			while(*pKey != '\0')
			{
				n += (*pKey);
				pKey++;
			}
		}
		else
		{
			while(*pKey != '\0')
			{
				n += ((*pKey) & ~0x20);
				pKey++;
			}
		}
		return n % nBucketCount;
	}

	virtual bool AreKeysEqual(const char* pKey1, const char* pKey2)
	{
		if(m_bCaseSensitive)
			return(strcmp(pKey1, pKey2) == 0);
		else
			return(stricmp(pKey1, pKey2) == 0);
	}

	// Adds a key and value pair to the hash table.  The key should be a constant
	// string (or at least a string that won't change over the lifetime of the
	// hash table).  The GHeap class provides a good place to store such a
	// string.
	void Add(const char* pKey, const void* pValue)
	{
		_Add(pKey, pValue);
	}

	// Gets the value for the specified key
	bool Get(const char* pKey, void** ppOutValue)
	{
		return _Get(pKey, ppOutValue);
	}

	// Gets the value for the specified key
	bool Get(const char* pKey, int nLen, void** ppOutValue);

	// Removes an entry from the hash table
	void Remove(const char* pKey)
	{
		_Remove(pKey);
	}
};



// Hash table based on keys of constant strings (or at least strings
// that won't change during the lifetime of the hash table).  It's a
// good idea to use a GHeap in connection with this class.
class GConstStringToIntsHashTable : public GHashTableBase
{
protected:
	bool m_bCaseSensitive;

public:
	GConstStringToIntsHashTable(int nInitialBucketCount, bool bCaseSensitive)
		: GHashTableBase(nInitialBucketCount)
	{
		m_bCaseSensitive = bCaseSensitive;
	}

	virtual ~GConstStringToIntsHashTable()
	{
	}

	virtual unsigned int Hash(const char* pKey, int nBucketCount)
	{
		unsigned int n = 0;
		if(m_bCaseSensitive)
		{
			while(*pKey != '\0')
			{
				n += (*pKey);
				pKey++;
			}
		}
		else
		{
			while(*pKey != '\0')
			{
				n += ((*pKey) & ~0x20);
				pKey++;
			}
		}
		return n % nBucketCount;
	}

	virtual bool AreKeysEqual(const char* pKey1, const char* pKey2)
	{
		if(m_bCaseSensitive)
			return(strcmp(pKey1, pKey2) == 0);
		else
			return(stricmp(pKey1, pKey2) == 0);
	}

	// Adds a key and value pair to the hash table.  The key should be a constant
	// string (or at least a string that won't change over the lifetime of the
	// hash table).  The GHeap class provides a good place to store such a
	// string.
	void Add(const char* pKey, int nValue)
	{
		uintptr_t tmp = nValue;
		_Add(pKey, (const void*)tmp);
	}

	// Gets the value for the specified key
	bool Get(const char* pKey, int* pValue)
	{
		uintptr_t tmp;
		bool bRet = _Get(pKey, (void**)(void*)&tmp);
		*pValue = (int)tmp;
		return bRet;
	}

	// Gets the value for the specified key
	bool Get(const char* pKey, int nLen, int* pValue);

	// Removes an entry from the hash table
	void Remove(const char* pKey)
	{
		_Remove(pKey);
	}
};


#endif // __GHASHTABLE_H__
